package sort;

/**
 * @author: zhs
 * @since: 2021/6/10 15:53
 */
public class AllSortDemo {
    /**
     * 每次选择一个元素，并且将这个元素和整个数组中的所有元素进行比较，然后插入到合适的位置，图片演示如上，时间复杂度 O(n^2)
     * @param arr
     * @param length
     */
    void insertion_sort(int arr[], int length)
    {
        int i,j;
        for (i = 1; i < length; i++) {
            int tmp = arr[i];
            for (j = i; j > 0 && arr[j - 1] > tmp; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = tmp;
        }
    }

    /**
     * 这个是插入排序的修改版，根据步长由长到短分组，进行排序，直到步长为1为止，属于插入排序的一种。
     * @param arr
     * @param n
     * @return
     */
    int shellSort(int arr[], int n)
    {
        for (int gap = n/2; gap > 0; gap /= 2)
        {
            for (int i = gap; i < n; i += 1)
            {
                int temp = arr[i];
                int j;
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                    arr[j] = arr[j - gap];
                arr[j] = temp;
            }
        }
        return 0;
    }



    int getMax(int arr[], int n)
    {
        int mx = arr[0];
        for (int i = 1; i < n; i++)
            if (arr[i] > mx)
                mx = arr[i];
        return mx;
    }

    void countSort(int arr[], int n, int exp)
    {
        int[] output = new int[n];
        int i;
        int[] count = new int[10];

        for (i = 0; i < n; i++)
            count[ (arr[i]/exp)%10 ]++;

        for (i = 1; i < 10; i++)
            count[i] += count[i - 1];

        for (i = n - 1; i >= 0; i--)
        {
            output[count[ (arr[i]/exp)%10 ] - 1] = arr[i];
            count[ (arr[i]/exp)%10 ]--;
        }

        for (i = 0; i < n; i++)
            arr[i] = output[i];
    }

    /**
     * 基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。排序过程是将所有待比较数值统一为同样的数位长度，数位较短的数前面补零，然后从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
     *
     *
     * @param arr
     * @param n
     */
    void radixsort(int arr[], int n)
    {
        int m = getMax(arr, n);
        for (int exp = 1; m/exp > 0; exp *= 10)
            countSort(arr, n, exp);
    }

    /**
     * 冒泡排序
     * @param a
     */
    void bubbleSort(int a[])
    {
        boolean swapp = true;
        while(swapp){
            swapp = false;
            for (int i = 0; i < a.length-1; i++) {
                if (a[i]>a[i+1] ){
                    a[i] += a[i+1];
                    a[i+1] = a[i] - a[i+1];
                    a[i] -=a[i+1];
                    swapp = true;
                }
            }
        }
    }





}
